package binarytree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author liangzai
 * @Description:
 */
public class BinaryTree {
    //非递归前序遍历二叉树
    public void preOrderNor(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pcur = root;
        while(pcur!=null || !stack.isEmpty()){
            while(pcur!=null){
                stack.push(pcur);
                pcur = pcur.left;
                System.out.print(stack.peek().val+" ");
            }
            pcur = stack.pop().right;
        }
        System.out.println();
    }

    //非递归中序遍历二叉树
    public void inOrderNor(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pcur = root;
        while(pcur!=null || !stack.isEmpty()){
            while(pcur!=null){
                stack.push(pcur);
                pcur = pcur.left;
            }
            System.out.print(stack.peek().val+" ");
            pcur = stack.pop().right;
        }
        System.out.println();
    }

    //判断是否是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root==null){
            return true;
        }
        int flag = 0;
        Queue<TreeNode> list = new LinkedList<>();
        list.offer(root);
        while(flag==0){
            TreeNode pcur = list.poll();
            if(pcur==null) {
                int size = list.size();
                for (int i = 0; i < size; i++) {
                    if(list.poll()!=null) {
                        return false;
                    }
                }
                break;
            }
            list.offer(pcur.left);
            list.offer(pcur.right);
        }
        return true;
    }

    //根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }

    private StringBuilder tree2strChild(TreeNode root ,StringBuilder stringBuilder){
        if(root==null){
            return null;
        }
        stringBuilder.append(root.val);
        if(root.left!=null){
            stringBuilder.append('(');
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(')');
        }else{
            if(root.right!=null){
                stringBuilder.append("()");
            }else{
                return null;
            }
        }
        if(root.right!=null){
            stringBuilder.append('(');
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(')');
        }else{
            return null;
        }
        return stringBuilder;
    }

}
